home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: Alpha / Whiteline Alpha.iso / progtool / c / tiff_lib / source / tif_lzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-22  |  28.2 KB  |  837 lines
  1. #pragma warn -use
  2. static char     *sccsid = "@(#)TIFF/tif_lzw.c 1.20, Copyright (c) Sam Leffler, Dieter Linde, "__DATE__;
  3. #pragma warn .use
  4. /*
  5.  * Copyright (c) 1988, 1990 by Sam Leffler, Oct 8 1990
  6.  * All rights reserved.
  7.  *
  8.  * This file is provided for unrestricted use provided that this legend is included on all tape media and as a part of the
  9.  * software program in whole or part.  Users may copy, modify or distribute this file at will.
  10.  *
  11.  * TIFF Library.
  12.  *
  13.  * Rev 5.0 Lempel-Ziv & Welch Compression Support
  14.  *
  15.  * Copyright (c) 1985, 1986 The Regents of the University of California.
  16.  * All rights reserved.
  17.  *
  18.  * This code is derived from software contributed to Berkeley by James A. Woods, derived from original work by Spencer Thomas
  19.  * and Joseph Orost.
  20.  *
  21.  * Redistribution and use in source and binary forms are permitted provided that the above copyright notice and this paragraph are
  22.  * duplicated in all such forms and that any documentation, advertising materials, and other materials related to such
  23.  * distribution and use acknowledge that the software was developed by the University of California, Berkeley.  The name of the
  24.  * University may not be used to endorse or promote products derived from this software without specific prior written permission.
  25.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  26.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28. #include <stdio.h>
  29. #include <assert.h>
  30. #include "tiffio.h"
  31.  
  32. #define MAXCODE(n)    ((1 << (n)) - 1)
  33.  
  34. /*
  35.  * The TIFF spec specifies that encoded bit strings range from 9 to 12 bits.  This is somewhat unfortunate in that
  36.  * experience indicates full color RGB pictures often need ~14 bits for reasonable compression.
  37.  */
  38. #define BITS_MIN       9               /* start with 9 bits */
  39. #define BITS_MAX         12                /* max of 12 bit strings */
  40. /*** predefined codes ***/
  41. #define CODE_CLEAR         256             /* code to clear string table */
  42. #define CODE_EOI        257             /* end-of-information code */
  43. #define CODE_FIRST      258             /* first free code entry */
  44. #define CODE_MAX        MAXCODE(BITS_MAX)
  45. #if 0
  46. #define HSIZE           9001            /* 91% occupancy */
  47. #define HSHIFT          (8 - (16 - 13))
  48. #else
  49. #define HSIZE           5003            /* 80% occupancy */
  50. #define HSHIFT          (8 - (16 - 12))
  51. #endif
  52.  
  53. /*
  54.  * NB: The 5.0 spec describes a different algorithm than Aldus implements.  Specifically, Aldus does code length transitions
  55.  *     one code earlier than should be done (for real LZW).  Earlier versions of this library implemented the correct
  56.  *     LZW algorithm, but emitted codes in a bit order opposite to the TIFF spec.  Thus, to maintain compatibility w/ Aldus
  57.  *     we interpret MSB-LSB ordered codes to be images written w/ old versions of this library, but otherwise adhere to the
  58.  *     Aldus "off by one" algorithm.
  59.  *
  60.  * Future revisions to the TIFF spec are expected to "clarify this issue".
  61.  */
  62. #define SetMaxCode(sp, v)    { \
  63.                         (sp)->lzw_maxcode = (v) - 1; \
  64.                         if ((sp)->lzw_flags & LZW_COMPAT) \
  65.                                 (sp)->lzw_maxcode++; \
  66.                 }
  67.  
  68. /*
  69.  * Decoding-specific state.
  70.  */
  71. struct decode {
  72.            short      prefixtab[HSIZE];              /* prefix(code) */
  73.         u_char  suffixtab[CODE_MAX + 1];      /* suffix(code) */
  74.         u_char  stack[HSIZE - (CODE_MAX + 1)];
  75.         u_char  *stackp;                    /* stack pointer */
  76.         int     firstchar;                  /* of string associated w/ last code */
  77. };
  78.  
  79. /*
  80.  * Encoding-specific state.
  81.  */
  82. struct encode {
  83.         long       checkpoint;                 /* point at which to clear table */
  84. #define    CHECK_GAP    10000               /* enc_ratio check interval */
  85.         long    ratio;                      /* current compression ratio */
  86.         long    incount;                    /* (input) data bytes encoded */
  87.         long    outcount;                   /* encoded (output) bytes */
  88.         long    htab[HSIZE];                /* hash table */
  89.         short   codetab[HSIZE];             /* code table */
  90. };
  91.  
  92. /*
  93.  * State block for each open TIFF file using LZW compression/decompression.
  94.  */
  95. typedef struct {
  96.         int     lzw_oldcode;                /* last code encountered */
  97.         u_char  lzw_hordiff;
  98. #define LZW_HORDIFF4    0x01                /* hor. diff w/ 4-bit samples */
  99. #define LZW_HORDIFF8    0x02                /* hor. diff w/ 8-bit samples */
  100. #define LZW_HORDIFF16   0x04                /* hor. diff w/ 16-bit samples */
  101. #define LZW_HORDIFF32   0x08                /* hor. diff w/ 32-bit samples */
  102.         u_char  lzw_flags;
  103. #define LZW_RESTART     0x01                /* restart interrupted decode */
  104. #define LZW_COMPAT      0x02                /* read old bit-reversed codes */
  105.         u_short lzw_nbits;                  /* number of bits/code */
  106.         u_short lzw_stride;                 /* horizontal diferencing stride */
  107.         int     lzw_maxcode;                /* maximum code for lzw_nbits */
  108.         long    lzw_bitoff;                 /* bit offset into data */
  109.         long    lzw_bitsize;                /* size of strip in bits */
  110.         int     lzw_free_ent;               /* next free entry in hash table */
  111.         union {
  112.                 struct decode    dec;
  113.                 struct encode     enc;
  114.         } u;
  115. } LZWState;
  116.  
  117. #define dec_prefix         u.dec.prefixtab
  118. #define dec_suffix      u.dec.suffixtab
  119. #define dec_stack       u.dec.stack
  120. #define dec_stackp      u.dec.stackp
  121. #define dec_firstchar   u.dec.firstchar
  122.  
  123. #define enc_checkpoint  u.enc.checkpoint
  124. #define enc_ratio       u.enc.ratio
  125. #define enc_incount     u.enc.incount
  126. #define enc_outcount    u.enc.outcount
  127. #define enc_htab        u.enc.htab
  128. #define enc_codetab     u.enc.codetab
  129.  
  130. /*
  131.  * Masks for extracting/inserting variable length bit codes.
  132.  */
  133. static u_char    rmask[9] = { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
  134. static u_char     lmask[9] = { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  135.  
  136. /****************************************************************************
  137.  *
  138.  */
  139. static int
  140. LZWCheckPredictor(
  141.            TIFF         *tif,
  142.         LZWState    *sp
  143.         )
  144. {
  145.         TIFFDirectory *td = &tif->tif_dir;
  146.  
  147.         switch (td->td_predictor) {
  148.             case 1:
  149.                     break;
  150.             case 2:
  151.                     sp->lzw_stride = (td->td_planarconfig == PLANARCONFIG_CONTIG ? td->td_samplesperpixel : 1);
  152.                     if (td->td_bitspersample == 8) {
  153.                             sp->lzw_hordiff = LZW_HORDIFF8;
  154.                             break;
  155.                     }
  156.                     if (td->td_bitspersample == 16) {
  157.                             sp->lzw_hordiff = LZW_HORDIFF16;
  158.                             break;
  159.                     }
  160.                     TIFFError(tif->tif_name, "Horizontal differencing \"Predictor\" not supported with %d-bit samples", td->td_bitspersample);
  161.                     return(0);
  162.             default:
  163.                     TIFFError(tif->tif_name, "\"Predictor\" value %d not supported", td->td_predictor);
  164.                     return(0);
  165.         }
  166.         return(1);
  167. }
  168.  
  169. /*
  170.  * LZW Decoder.
  171.  */
  172.  
  173. /****************************************************************************
  174.  * Setup state for decoding a strip.
  175.  */
  176. static int
  177. LZWPreDecode(
  178.            TIFF     *tif
  179.            )
  180. {
  181.         register LZWState    *sp = (LZWState *)tif->tif_data;
  182.         register int         code;
  183.  
  184.         if (sp == NULL) {
  185.                 if ((tif->tif_data = malloc(sizeof(LZWState))) == NULL) {
  186.                         TIFFError("LZWPreDecode", "No space for LZW state block");
  187.                            return(0);
  188.                 }
  189.                 sp = (LZWState *)tif->tif_data;
  190.                 sp->lzw_flags = 0;
  191.                 sp->lzw_hordiff = 0;
  192.                 if (!LZWCheckPredictor(tif, sp))
  193.                         return(0);
  194.         } 
  195.         else
  196.                 sp->lzw_flags &= ~LZW_RESTART;
  197.         sp->lzw_nbits = BITS_MIN;
  198.  
  199.         /*
  200.          * Pre-load the table.
  201.          */
  202.         for (code = 255; code >= 0; code--)
  203.                    sp->dec_suffix[code] = (u_char)code;
  204.         sp->lzw_free_ent = CODE_FIRST;
  205.         sp->lzw_bitoff = 0;
  206.  
  207.         /* 
  208.          * Calculate data size in bits.
  209.          */
  210.         sp->lzw_bitsize = tif->tif_rawdatasize;
  211.         sp->lzw_bitsize = (sp->lzw_bitsize << 3) - (BITS_MAX - 1);
  212.         sp->dec_stackp = sp->dec_stack;
  213.         sp->lzw_oldcode = -1;
  214.         sp->dec_firstchar = -1;
  215.  
  216.         /*
  217.          * Check for old bit-reversed codes.  All the flag manipulations are to insure only one warning is
  218.          * given for a file.
  219.          */
  220.         if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) {
  221.                    if ((sp->lzw_flags & LZW_COMPAT) == 0)
  222.                            TIFFWarning(tif->tif_name, "Old-style LZW codes, convert file");
  223.                 sp->lzw_flags |= LZW_COMPAT;
  224.         } 
  225.         else
  226.                 sp->lzw_flags &= ~LZW_COMPAT;
  227.         SetMaxCode(sp, MAXCODE(BITS_MIN));
  228.         return(1);
  229. }
  230.  
  231. #define REPEAT4(n, op)    switch (n) { \
  232.                     default: { \
  233.                         int     i; \
  234.                     \
  235.                         for (i = n - 4; i > 0; i--) { \
  236.                             op; \
  237.                         } \
  238.                     } \
  239.                     case 4: \
  240.                         op; \
  241.                     case 3: \
  242.                         op; \
  243.                  case 2: \
  244.                      op; \
  245.                     case 1: \
  246.                         op; \
  247.                     case 0: \
  248.                         ; \
  249.                 }
  250.  
  251. /****************************************************************************
  252.  *
  253.  */
  254. static void
  255. horizontalAccumulate8(
  256.            register char    *cp,
  257.         register int     cc,
  258.         register int     stride
  259.         )
  260. {
  261.         if (cc > stride) {
  262.                 cc -= stride;
  263.                 do {
  264.                         REPEAT4(stride, cp[stride] += cp[0]; cp++)
  265.                         cc -= stride;
  266.                 } while (cc > 0);
  267.         }
  268. }
  269.  
  270. /****************************************************************************
  271.  *
  272.  */
  273. static void
  274. horizontalAccumulate16(
  275.         register short    *wp,
  276.         register int     wc,
  277.         register int     stride
  278.         )
  279. {
  280.         if (wc > stride) {
  281.                    wc -= stride;
  282.                 do {
  283.                            REPEAT4(stride, wp[stride] += wp[0]; wp++)
  284.                         wc -= stride;
  285.                 } while (wc > 0);
  286.         }
  287. }
  288.  
  289. /****************************************************************************
  290.  * Get the next code from the raw data buffer.
  291.  */
  292. static int
  293. GetNextCode(
  294.         TIFF     *tif
  295.         )
  296. {
  297.         register LZWState    *sp = (LZWState *)tif->tif_data;
  298.         register int         code, bits;
  299.         register long         r_off;
  300.         register u_char     *bp;
  301.  
  302.         /*
  303.          * This check shouldn't be necessary because each strip is suppose to be terminated with CODE_EOI.
  304.          * At worst it's a substitute for the CODE_EOI that's supposed to be there (see calculation of lzw_bitsize
  305.          * in LZWPreDecode()).
  306.          */
  307.         if (sp->lzw_bitoff > sp->lzw_bitsize) {
  308.                 TIFFWarning(tif->tif_name, "LZWDecode: Strip %d not terminated with EOI code", tif->tif_curstrip);
  309.                 return(CODE_EOI);
  310.         }
  311.         r_off = sp->lzw_bitoff;
  312.         bits = sp->lzw_nbits;
  313.  
  314.         /*
  315.          * Get to the first byte.
  316.          */
  317.         bp = (u_char *)tif->tif_rawdata + (r_off >> 3);
  318.         r_off &= 7;
  319.         if (sp->lzw_flags & LZW_COMPAT) {
  320.  
  321.     /* 
  322.      * Get first part (low order bits).
  323.      */
  324.                 code = (*bp++ >> r_off);
  325.                 r_off = 8 - r_off;                 /* now, offset into code word */
  326.                 bits -= (int)r_off;
  327.  
  328.     /* 
  329.      * Get any 8 bit parts in the middle (<=1 for up to 16 bits). 
  330.      */
  331.                 if (bits >= 8) {
  332.                         code |= (*bp++ << r_off);
  333.                         r_off += 8;
  334.                         bits -= 8;
  335.                 }
  336.  
  337.     /* 
  338.      * High order bits. 
  339.      */
  340.                 code |= ((*bp & rmask[bits]) << r_off);
  341.         } 
  342.         else {
  343.                 r_off = 8 - r_off;                 /* convert offset to count */
  344.                 code = *bp++ & rmask[r_off];       /* high order bits */
  345.                 bits -= (int)r_off;
  346.                 if (bits >= 8) {
  347.                         code = (code << 8) | *bp++;
  348.                         bits -= 8;
  349.                 }
  350.  
  351.     /* 
  352.      * Low order bits.
  353.      */
  354.                 code = (code << bits) | ((*bp & lmask[bits]) >> (8 - bits));
  355.         }
  356.         sp->lzw_bitoff += sp->lzw_nbits;
  357.         return(code);
  358. }
  359.  
  360. /****************************************************************************
  361.  * Decode the next scanline.
  362.  */
  363. static int
  364. LZWDecode(
  365.            TIFF    *tif,
  366.         u_char     *op0,
  367.         int    occ0
  368.         )
  369. {
  370.         register char        *op = (char *)op0;
  371.         register int         occ = occ0;
  372.         register LZWState     *sp = (LZWState *)tif->tif_data;
  373.         register int         code;
  374.         register u_char     *stackp;
  375.         int             firstchar, oldcode, incode;
  376.  
  377.         stackp = sp->dec_stackp;
  378.  
  379.         /*
  380.          * Restart interrupted unstacking operations.
  381.          */
  382.         if (sp->lzw_flags & LZW_RESTART) {
  383.                 do {
  384.                         if (--occ < 0) {           /* end of scanline */
  385.                                 sp->dec_stackp = stackp;
  386.                                 return(1);
  387.                         }
  388.                         *op++ = *--stackp;
  389.                 } while (stackp > sp->dec_stack);
  390.                 sp->lzw_flags &= ~LZW_RESTART;
  391.         }
  392.         oldcode = sp->lzw_oldcode;
  393.         firstchar = sp->dec_firstchar;
  394.         while (occ > 0 && (code = GetNextCode(tif)) != CODE_EOI) {
  395.                 if (code == CODE_CLEAR) {
  396.                         bzero(sp->dec_prefix, sizeof(sp->dec_prefix));
  397.                         sp->lzw_free_ent = CODE_FIRST;
  398.                         sp->lzw_nbits = BITS_MIN;
  399.                         SetMaxCode(sp, MAXCODE(BITS_MIN));
  400.                         if ((code = GetNextCode(tif)) == CODE_EOI)
  401.                                 break;
  402.                         *op++ = code;
  403.                         occ--;
  404.                         oldcode = firstchar = code;
  405.                         continue;
  406.                 }
  407.                 incode = code;
  408.  
  409.     /*
  410.          * When a code is not in the table we use (as spec'd):  StringFromCode(oldcode) + FirstChar(StringFromCode(oldcode))
  411.          */
  412.                 if (code >= sp->lzw_free_ent) {    /* code not in table */
  413.                         *stackp++ = firstchar;
  414.                         code = oldcode;
  415.                 }
  416.  
  417.     /*
  418.          * Generate output string (first in reverse).
  419.          */
  420.                 for (; code >= 256; code = sp->dec_prefix[code])
  421.                         *stackp++ = sp->dec_suffix[code];
  422.                 *stackp++ = firstchar = sp->dec_suffix[code];
  423.                 do {
  424.                         if (--occ < 0) {           /* end of scanline */
  425.                                 sp->lzw_flags |= LZW_RESTART;
  426.                                 break;
  427.                         }
  428.                         *op++ = *--stackp;
  429.                 } while (stackp > sp->dec_stack);
  430.  
  431.     /*
  432.          * Add the new entry to the code table.
  433.          */
  434.                 if ((code = sp->lzw_free_ent) < CODE_MAX) {
  435.                         sp->dec_prefix[code] = (u_short)oldcode;
  436.                         sp->dec_suffix[code] = firstchar;
  437.                         sp->lzw_free_ent++;
  438.  
  439.     /*
  440.          * If the next entry is too big for the current code size, then increase the
  441.          * size up to the maximum possible.
  442.          */
  443.                         if (sp->lzw_free_ent > sp->lzw_maxcode) {
  444.                                 sp->lzw_nbits++;
  445.                                 if (sp->lzw_nbits > BITS_MAX)
  446.                                         sp->lzw_nbits = BITS_MAX;
  447.                                 SetMaxCode(sp, MAXCODE(sp->lzw_nbits));
  448.                         }
  449.                 }
  450.                 oldcode = incode;
  451.         }
  452.         sp->dec_stackp = stackp;
  453.         sp->lzw_oldcode = oldcode;
  454.         sp->dec_firstchar = firstchar;
  455.         switch (sp->lzw_hordiff) {
  456.             case LZW_HORDIFF8:
  457.                     horizontalAccumulate8((char *)op0, occ0, sp->lzw_stride);
  458.                     break;
  459.             case LZW_HORDIFF16:
  460.                     horizontalAccumulate16((short *)op0, occ0 / 2, sp->lzw_stride);
  461.                     break;
  462.         }
  463.         if (occ > 0) {
  464.                 TIFFError(tif->tif_name, "LZWDecode: Not enough data for scanline %d (decode %d bytes)", tif->tif_row, occ);
  465.                 return(0);
  466.         }
  467.         return(1);
  468. }
  469.  
  470. /*
  471.  * LZW Encoding.
  472.  */
  473.  
  474. /****************************************************************************
  475.  * Reset code table.
  476.  */
  477. static void
  478. cl_hash(
  479.            LZWState    *sp
  480.            )
  481. {
  482.         register long    *htab_p = sp->enc_htab + HSIZE;
  483.         register long     i;
  484.         register long    m1 = -1;
  485.  
  486.         i = HSIZE - 16;
  487.         do {
  488.                 *(htab_p - 16) = m1;
  489.                 *(htab_p - 15) = m1;
  490.                 *(htab_p - 14) = m1;
  491.                 *(htab_p - 13) = m1;
  492.                 *(htab_p - 12) = m1;
  493.                 *(htab_p - 11) = m1;
  494.                 *(htab_p - 10) = m1;
  495.                 *(htab_p - 9) = m1;
  496.                 *(htab_p - 8) = m1;
  497.                 *(htab_p - 7) = m1;
  498.                 *(htab_p - 6) = m1;
  499.                 *(htab_p - 5) = m1;
  500.                 *(htab_p - 4) = m1;
  501.                 *(htab_p - 3) = m1;
  502.                 *(htab_p - 2) = m1;
  503.                 *(htab_p - 1) = m1;
  504.                 htab_p -= 16;
  505.         } while ((i -= 16) >= 0);
  506.         for (i += 16; i > 0; i--)
  507.                 *--htab_p = m1;
  508. }
  509.  
  510. /****************************************************************************
  511.  * Reset encoding state at the start of a strip.
  512.  */
  513. static int
  514. LZWPreEncode(
  515.         TIFF     *tif
  516.         )
  517. {
  518.         register LZWState    *sp = (LZWState *)tif->tif_data;
  519.  
  520.         if (sp == NULL) {
  521.                 if ((tif->tif_data = malloc(sizeof(LZWState))) == NULL) {
  522.                         TIFFError("LZWPreEncode", "No space for LZW state block");
  523.                         return(0);
  524.                 }
  525.                 sp = (LZWState *)tif->tif_data;
  526.                 sp->lzw_flags = 0;
  527.                 sp->lzw_hordiff = 0;
  528.                 if (!LZWCheckPredictor(tif, sp))
  529.                         return(0);
  530.         }
  531.         sp->enc_ratio = 0;
  532.         sp->enc_checkpoint = CHECK_GAP;
  533.         SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN) + 1);
  534.         sp->lzw_free_ent = CODE_FIRST;
  535.         sp->lzw_bitoff = 0;
  536.         sp->lzw_bitsize = (tif->tif_rawdatasize << 3) - (BITS_MAX - 1);
  537.         cl_hash(sp);                   /* clear hash table */
  538.         sp->lzw_oldcode = -1;       /* generates CODE_CLEAR in LZWEncode */
  539.         return(1);
  540. }
  541.  
  542. /****************************************************************************
  543.  *
  544.  */
  545. static void
  546. horizontalDifference8(
  547.         register char    *cp,
  548.         register int     cc,
  549.         register int     stride
  550.         )
  551. {
  552.         if (cc > stride) {
  553.                 cc -= stride;
  554.                 cp += cc - 1;
  555.                 do {
  556.                         REPEAT4(stride, cp[stride] -= cp[0]; cp--)
  557.                         cc -= stride;
  558.                 } while (cc > 0);
  559.         }
  560. }
  561.  
  562. /****************************************************************************
  563.  *
  564.  */
  565. static void
  566. horizontalDifference16(
  567.         register short    *wp,
  568.         register int     wc,
  569.         register int     stride
  570.         )
  571. {
  572.         if (wc > stride) {
  573.                 wc -= stride;
  574.                 wp += wc - 1;
  575.                 do {
  576.                         REPEAT4(stride, wp[stride] -= wp[0]; wp--)
  577.                         wc -= stride;
  578.                 } while (wc > 0);
  579.         }
  580. }
  581.  
  582. /****************************************************************************
  583.  *
  584.  */
  585. static void
  586. PutNextCode(
  587.         TIFF     *tif,
  588.         int     c
  589.         )
  590. {
  591.         register LZWState    *sp = (LZWState *)tif->tif_data;
  592.         register long         r_off;
  593.         register int         bits;
  594.         register int        code = c;
  595.         register u_char     *bp;
  596.  
  597.         r_off = sp->lzw_bitoff;
  598.         bits = sp->lzw_nbits;
  599.  
  600.     /*
  601.          * Flush buffer if code doesn't fit.
  602.          */
  603.         if (r_off + bits > sp->lzw_bitsize) {
  604.  
  605.     /*
  606.          * Calculate the number of full bytes that can be written and save anything else for the next write.
  607.          */
  608.                 if (r_off & 7) {
  609.                         tif->tif_rawcc = r_off >> 3;
  610.                         bp = tif->tif_rawdata + tif->tif_rawcc;
  611.                           TIFFFlushData1(tif);
  612.                         tif->tif_rawdata[0] = *bp;
  613.                 } 
  614.                 else {
  615.  
  616.        /*
  617.          * Otherwise, on a byte boundary (in which tiff_rawcc is already correct).
  618.          */
  619.                          TIFFFlushData1(tif);
  620.                 }
  621.                 bp = tif->tif_rawdata;
  622.                 sp->lzw_bitoff = (r_off &= 7);
  623.         } 
  624.         else {
  625.  
  626.     /*
  627.          * Get to the first byte.
  628.          */
  629.                 bp = tif->tif_rawdata + (r_off >> 3);
  630.                 r_off &= 7;
  631.         }
  632.  
  633.         /*
  634.          * Note that lzw_bitoff is maintained as the bit offset into the buffer w/ a right-to-left orientation (i.e.
  635.          * lsb-to-msb).  The bits, however, go in the file in an msb-to-lsb order.
  636.          */
  637.         bits -= (int)(8 - r_off);
  638.         *bp = (*bp & lmask[r_off]) | (code >> bits);
  639.         bp++;
  640.         if (bits >= 8) {
  641.                 bits -= 8;
  642.                 *bp++ = (code >> bits);
  643.         }
  644.         if (bits)
  645.                 *bp = (code & rmask[bits]) << (8 - bits);
  646.  
  647.         /*
  648.          * enc_outcount is used by the compression analysis machinery which resets the compression tables when the compression
  649.          * ratio goes up.  lzw_bitoff is used here (in PutNextCode) for inserting codes into the output buffer.  tif_rawcc must
  650.          * be updated for the mainline write code in TIFFWriteScanline() so that data is flushed when the end of a strip is reached.
  651.          * Note that the latter is rounded up to ensure that a non-zero byte count is present.
  652.          */
  653.         sp->enc_outcount += sp->lzw_nbits;
  654.         sp->lzw_bitoff += sp->lzw_nbits;
  655.         tif->tif_rawcc = (sp->lzw_bitoff + 7) >> 3;
  656. }
  657.  
  658. /****************************************************************************
  659.  * Check compression ratio and, if things seem to be slipping, clear the hash table and reset state.
  660.  */
  661. static void
  662. cl_block(
  663.         TIFF     *tif
  664.         )
  665. {
  666.         register LZWState    *sp = (LZWState *)tif->tif_data;
  667.         register long         rat;
  668.  
  669.         sp->enc_checkpoint = sp->enc_incount + CHECK_GAP;
  670.         if (sp->enc_incount > 0x007fffffL) {        /* shift will overflow */
  671.                 rat = sp->enc_outcount >> 8;
  672.                 rat = (rat == 0 ? 0x7fffffffL : sp->enc_incount / rat);
  673.         } 
  674.         else
  675.                 rat = (sp->enc_incount << 8) / sp->enc_outcount;    /* 8 fract bits */
  676.         if (rat <= sp->enc_ratio) {
  677.                 sp->enc_ratio = 0;
  678.                 cl_hash(sp);
  679.                 sp->lzw_free_ent = CODE_FIRST;
  680.                 PutNextCode(tif, CODE_CLEAR);
  681.                 SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN) + 1);
  682.         } 
  683.         else
  684.                 sp->enc_ratio = rat;
  685. }
  686.  
  687. #pragma warn -aus
  688. /****************************************************************************
  689.  * Encode a scanline of pixels.
  690.  *
  691.  * Uses an open addressing double hashing (no chaining) on the prefix code/next character combination.  We do a variant of
  692.  * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime secondary probe.  Here, the modular division
  693.  * first probe is gives way to a faster exclusive-or manipulation.  Also do block compression with an adaptive reset, whereby the
  694.  * code table is cleared when the compression ratio decreases, but after the table fills.  The variable-length output codes
  695.  * are re-sized at this point, and a CODE_CLEAR is generated for the decoder.
  696.  */
  697. static int
  698. LZWEncode(
  699.         TIFF     *tif,
  700.         u_char     *bp,
  701.         int     cc
  702.         )
  703. {
  704.         static char        module[] = "LZWEncode";
  705.         register LZWState    *sp;
  706.         register long         fcode;
  707.         register int         h, c, ent, disp;
  708.  
  709.         if ((sp = (LZWState *)tif->tif_data) == NULL)
  710.                 return(0);
  711.     /*** XXX horizontal differencing alters user's data XXX ***/
  712.         switch (sp->lzw_hordiff) {
  713.             case LZW_HORDIFF8:
  714.                     horizontalDifference8((char *)bp, cc, sp->lzw_stride);
  715.                     break;
  716.             case LZW_HORDIFF16:
  717.                     horizontalDifference16((short *)bp, cc / 2, sp->lzw_stride);
  718.                     break;
  719.         }
  720.         ent = sp->lzw_oldcode;
  721.         if (ent == -1 && cc > 0) {
  722.                 PutNextCode(tif, CODE_CLEAR);
  723.                 ent = *bp++; 
  724.                 cc--; 
  725.                 sp->enc_incount++;
  726.         }
  727.         while (cc > 0) {
  728.                 c = *bp++; 
  729.                 cc--; 
  730.                 sp->enc_incount++;
  731.                 fcode = ((long)c << BITS_MAX) + ent;
  732.                 h = (c << HSHIFT) ^ ent;           /* xor hashing */
  733.                 if (sp->enc_htab[h] == fcode) {
  734.                         ent = sp->enc_codetab[h];
  735.                         continue;
  736.                 }
  737.                 if (sp->enc_htab[h] >= 0) {
  738.  
  739.     /*
  740.          * Primary hash failed, check secondary hash.
  741.          */
  742.                         disp = HSIZE - h;
  743.                         if (h == 0)
  744.                                 disp = 1;
  745.                         do {
  746.                                 if ((h -= disp) < 0)
  747.                                         h += HSIZE;
  748.                                 if (sp->enc_htab[h] == fcode) {
  749.                                         ent = sp->enc_codetab[h];
  750.                                         goto hit;
  751.                                 }
  752.                         } while (sp->enc_htab[h] >= 0);
  753.                 }
  754.  
  755.     /*
  756.          * New entry, emit code and add to table.
  757.          */
  758.                 PutNextCode(tif, ent);
  759.                 ent = c;
  760.                 sp->enc_codetab[h] = sp->lzw_free_ent++;
  761.                 sp->enc_htab[h] = fcode;
  762.                 if (sp->lzw_free_ent == CODE_MAX - 1) {
  763.                         /*** table is full, emit clear code and reset ***/
  764.                         sp->enc_ratio = 0;
  765.                         cl_hash(sp);
  766.                         sp->lzw_free_ent = CODE_FIRST;
  767.                         PutNextCode(tif, CODE_CLEAR);
  768.                         SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN) + 1);
  769.                 } 
  770.                 else {
  771.                         if (sp->enc_incount >= sp->enc_checkpoint)
  772.                                 cl_block(tif);
  773.  
  774.     /*
  775.          * If the next entry is going to be too big for the code size, then increase it, if possible.
  776.          */
  777.                         if (sp->lzw_free_ent > sp->lzw_maxcode) {
  778.                                 sp->lzw_nbits++;
  779.                                 assert(sp->lzw_nbits <= BITS_MAX);
  780.                                 SetMaxCode(sp, MAXCODE(sp->lzw_nbits) + 1);
  781.                         }
  782.                 }
  783. hit:
  784.                 ;
  785.         }
  786.         sp->lzw_oldcode = ent;
  787.         return(1);
  788. }
  789. #pragma warn .aus
  790.  
  791. /****************************************************************************
  792.  * Finish off an encoded strip by flushing the last string and tacking on an End Of Information code.
  793.  */
  794. static int
  795. LZWPostEncode(
  796.         TIFF     *tif
  797.         )
  798. {
  799.         LZWState    *sp = (LZWState *)tif->tif_data;
  800.  
  801.         if (sp->lzw_oldcode != -1)
  802.                 PutNextCode(tif, sp->lzw_oldcode);
  803.         PutNextCode(tif, CODE_EOI);
  804.         return(1);
  805. }
  806.  
  807. /****************************************************************************
  808.  *
  809.  */
  810. static void
  811. LZWCleanup(
  812.         TIFF     *tif
  813.         )
  814. {
  815.         if (tif->tif_data) {
  816.                 free(tif->tif_data);
  817.                 tif->tif_data = NULL;
  818.         }
  819. }
  820.  
  821. /****************************************************************************
  822.  *
  823.  */
  824. int
  825. TIFFInitLZW(
  826.            TIFF    *tif
  827.            )
  828. {
  829.         tif->tif_stripdecode = LZWPreDecode;
  830.         tif->tif_decoderow = LZWDecode;
  831.         tif->tif_stripencode = LZWPreEncode;
  832.         tif->tif_encoderow = LZWEncode;
  833.         tif->tif_encodestrip = LZWPostEncode;
  834.         tif->tif_cleanup = LZWCleanup;
  835.         return(1);
  836. }
  837.